home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / info-service / gopher / Unix / GopherTools / jughead / jughead.0.9 / tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-19  |  15.4 KB  |  462 lines
  1. /*****************************************************************************
  2.  * File:    tree.c
  3.  *
  4.  * Author:    Rhett "Jonzy" Jones
  5.  *        jonzy@cc.utah.edu
  6.  *
  7.  * Date:    February 27, 1993
  8.  *
  9.  * Modified:    March 6, 1993, by Rhett "Jonzy" Jones
  10.  *         to support positions, by adding InList() and BuildList().
  11.  *        Also altered CreateBranch(), BuildTree(), and PrintTree().
  12.  *
  13.  *        March 9, 1993, by Rhett "Jonzy" Jones.
  14.  *        Modified BuildList() and added DestroyList(), and
  15.  *        NumberOfListNodes().
  16.  *
  17.  *        March 10, 1993, by Rhett "Jonzy" Jones.
  18.  *        Added BinarySearch(), LessOrEqual(), and NumberOfLeafs().
  19.  *
  20.  *        March 13, 1993, by Rhett "Jonzy" Jones.
  21.  *        Modified PrintTree(), so we can also print the host tree
  22.  *        in a more readable format, and added LongestStr2tab() and
  23.  *        PrintHostTree().
  24.  *
  25.  *        March 16, 1993, by Rhett "Jonzy" Jones.
  26.  *        Changed the type returned by BinarySearch() from a short
  27.  *        to a long.  Oops.
  28.  *
  29.  *        May 5, 1993, by Rhett "Jonzy" Jones.
  30.  *        Modified LessOrEqual() and BinarySearch() to support
  31.  *        partial word searches.
  32.  *
  33.  * Description:    Contains list, tree and binary tree routines.
  34.  *
  35.  * Routines:         short    InList(TreeType *node,long where);
  36.  *            void     DestroyList(ListType *list);
  37.  *        static    void     BuildList(TreeType *node,long where);
  38.  *        static    short     LessOrEqual(char *a,char *b,char * partialWord,size_t numChars);
  39.  *            long     BinarySearch(char *what2Find,Element *data,long size,
  40.  *                          char **asterik,size_t *asterikPos);
  41.  *            long     NumberOfLeafs(TreeType *node);
  42.  *        static    short    WhatDirection(char *s1,char *s2);
  43.  *            TreeType *WhatBranch(TreeType *node,char *word);
  44.  *        static    TreeType *CreateBranch(char *word,long where);
  45.  *            void     BuildTree(TreeType **root,char *word,long where);
  46.  *            long     NumberOfListNodes(ListType *positions);
  47.  *        static    int     LongestStr2tab(Tree *node);
  48.  *        static    void     PrintHostTree(Tree *node,int maxHostLen);
  49.  *            void     PrintTree(TreeType *node,int hostTree);
  50.  *
  51.  * Bugs:    No known bugs.
  52.  *
  53.  * Copyright:    Copyright 1993, University of Utah Computer Center.
  54.  *        This source may be freely distributed as long as this copyright
  55.  *         notice remains intact, and is in no way used for any monetary
  56.  *         gain, by any institution, business, person, or persons.
  57.  *
  58.  ****************************************************************************/
  59.  
  60. #include <stdio.h>
  61. #ifdef NEXT
  62. #    include <libc.h>
  63. #else
  64. #    include <stdlib.h>
  65. #endif
  66. #include <string.h>
  67. #include "tree.h"
  68.  
  69. #define GOLEFT        -1
  70. #define GORITE        1
  71. #define THISONE        0
  72. #define MAX(a,b)    ((a) > (b)) ? (a) : (b)
  73.  
  74. static short    limb = 0;        /* What limb do we insert on? */
  75.        TreeType    *root = (TreeType *)NIL;/* The root of the tree. */
  76. static TreeType    *lastNode = (TreeType *)NIL;    /* The last tree node we looked at. */
  77. static ListType    *lastList = (ListType *)NIL;    /* The last list node we looked at. */
  78.  
  79. extern long    lineNumber;        /* Defined in "dirTree.c". */
  80.  
  81. extern int    debug;            /* Defined in "jughead.c". */
  82.  
  83. /*****************************************************************************
  84.  * InList return true if 'where' is already in the list of the tree nodes.
  85.  * Otherwise if returns false.
  86.  ****************************************************************************/
  87. short InList(node,where)
  88.     TreeType    *node;        /* The tree node we looking at. */
  89.     long        where;        /* Index we are looking for. */
  90. {    ListType    *positions;    /* List with the indexes. */
  91.  
  92.     for (positions = node->positions; positions; positions = positions->next)
  93.         {
  94.         lastList = positions;
  95.         if (positions->where == where)
  96.             return(1);
  97.         }
  98.     return(0);
  99.  
  100. }    /* InList */
  101.  
  102. /*****************************************************************************
  103.  * DestroyList destroys the list 'list' by freeing up the memory occupied by
  104.  * the entire list.
  105.  ****************************************************************************/
  106. void DestroyList(list)
  107.     ListType    *list;    /* The list to destroy. */
  108. {    ListType    *node;    /* The node to free up. */
  109.  
  110.     while (list)
  111.         {
  112.         node = list;
  113.         list = list->next;
  114.         free(node);
  115.         }
  116.  
  117. }    /* DestroyList */
  118.  
  119. /*****************************************************************************
  120.  * BuildList returns the head of a list which gets built.  Each node contains
  121.  * 'where' and gets appended to the end of the list.
  122.  ****************************************************************************/
  123. ListType *BuildList(node,where)
  124.     ListType    *node;        /* The tree node we looking at. */
  125.     long        where;        /* Index we are looking for. */
  126. {    ListType    *positions;    /* List with the positions. */
  127.  
  128.     if (positions = (ListType *)malloc(sizeof(ListType)))
  129.         {
  130.         positions->where = where;
  131.         positions->next = (ListType *)NIL;
  132.         if (!node)
  133.             return(lastList = positions);
  134.         else
  135.             {
  136.             lastList->next = positions;
  137.             lastList = positions;
  138.             return(node);
  139.             }
  140.         }
  141.     else
  142.         fprintf(stderr,"error: BuildList could not get memory for the index.\n");
  143.  
  144.     return(node);        /* We better never get here. */
  145.  
  146. }    /* BuildList */
  147.  
  148. /*****************************************************************************
  149.  * LessOrEqual returns true if string 'a' is less than or equal to string 'b'.
  150.  * Either strncmp() or strcmp() is used for the string comparison depending
  151.  * on the value of 'partialWord'.
  152.  ****************************************************************************/
  153. static short LessOrEqual(a,b,partialWord,numChars)
  154.     char    *a,        /* The first string we a comparing. */
  155.         *b,        /* The other string we a comparing. */
  156.         *partialWord;    /* Is this a partial word search? */
  157.     size_t    numChars;    /* Number of characters to look at. */
  158. {
  159.     if (partialWord)
  160.         return(strncmp(a,b,numChars) <= 0);
  161.     else
  162.         return(strcmp(a,b) <= 0);
  163.  
  164. }    /* LessOrEqual */
  165.  
  166. /*****************************************************************************
  167.  * BinarySearch returns the position in 'data' where 'what2Find' exists or
  168.  * should exist.  The search is done when 'leftBounds' is greater than  or
  169.  * equal to 'rightBounds', or if we are doing a partial word search which
  170.  * 'asterik' tells us, we return as soon as strncmp() finds a match.
  171.  ****************************************************************************/
  172. long BinarySearch(what2Find,data,size,asterik,asterikPos)
  173.     char    *what2Find;    /* The string we are looking for. */
  174.     Element    *data;        /* An array of strings in sorted order. */
  175.     long    size;        /* The number of elements in 'data'. */
  176.     char    **asterik;    /* Do we have a partial word search? */
  177.     size_t    *asterikPos;    /* The position of the asterik. */
  178. {    long    leftBounds,    /* The left side of the search. */
  179.         rightBounds,    /* The right side of the search. */
  180.         midPoint;    /* The mid-point of the search. */
  181.  
  182.     /* See if this is a partial word search. */
  183.     if (*asterik = strchr(what2Find,'*'))
  184.         *asterikPos = (size_t)(*asterik - what2Find);
  185.  
  186.     /* Start the bounds as the entire array. */
  187.     leftBounds = 0;
  188.     rightBounds = size - 1;
  189.  
  190.     /* Keep finding the center of the bounds until the bounds converge. */
  191.     while (leftBounds < rightBounds)
  192.         {
  193.         midPoint = (leftBounds + rightBounds) / 2;
  194.         if (*asterik)
  195.             if (!strncmp(what2Find,data[midPoint].word,*asterikPos))
  196.                 return(midPoint);
  197.         if (LessOrEqual(what2Find,data[midPoint].word,*asterik,*asterikPos))
  198.             rightBounds = midPoint;
  199.         else
  200.             leftBounds = midPoint + 1;
  201.         }
  202.  
  203.     if (!strcmp(what2Find,data[leftBounds].word))
  204.         return(leftBounds);
  205.     else
  206.         return(-1);
  207.  
  208. }    /* BinarySearch */
  209.  
  210. /*****************************************************************************
  211.  * NumberOfLeafs returns the nuber of the leaves contained in the tree 'node'.
  212.  ****************************************************************************/
  213. long NumberOfLeafs(node)
  214.     TreeType    *node;        /* The node to have summed. */
  215. {
  216.     if (!node)
  217.         return(0);
  218.     else
  219.         return(1 + NumberOfLeafs(node->left) + NumberOfLeafs(node->right));
  220.  
  221. }    /* NumberOfLeafs */
  222.  
  223. /*****************************************************************************
  224.  * WhatDirection returns GOLEFT if 's1' is less than 's2', returns GORITE if
  225.  * if 's1' is greater than 's2', or returns THISONE if 's1' is the same as
  226.  * 's2'.
  227.  ****************************************************************************/
  228. static short WhatDirection(s1,s2)
  229.     char    *s1,            /* String contained in the leaf. */
  230.         *s2;            /* String we are looking for. */
  231. {    short    direction;        /* What direction do we look? */
  232.  
  233.     if ((direction = strcmp(s1,s2)) < 0)
  234.         return(GOLEFT);
  235.     else if (direction > 0)
  236.         return(GORITE);
  237.     else
  238.         return(THISONE);
  239.  
  240. }    /* WhatDirection */
  241.  
  242. /*****************************************************************************
  243.  * WhatBranch returns the limb of the tree containing 'word'.  This routine
  244.  * also assigns to 'limb' the direction we are looking in the tree and assigns
  245.  * to 'lastNode' the last node encountered.  These assignments are done to
  246.  * speed the time required when building the tree.
  247.  ****************************************************************************/
  248. TreeType *WhatBranch(node,word)
  249.     TreeType    *node;        /* The node we are looking at. */
  250.     char        *word;        /* The string we are looking for. */
  251. {
  252.     if (!node)        /* Insert at last position. */
  253.         return(node);
  254.     else switch (WhatDirection(word,node->word))
  255.         {
  256.         case GOLEFT:
  257.             limb = GOLEFT;
  258.             lastNode = node;
  259.             return(WhatBranch(node->left,word));
  260.         case GORITE:
  261.             limb = GORITE;
  262.             lastNode = node;
  263.             return(WhatBranch(node->right,word));
  264.         case THISONE:
  265.             return(node);
  266.         default:
  267.             fprintf(stderr,"warning: WhatBranch encountered bad default.\n");
  268.             return((TreeType *)NIL);    /* I hope not. */
  269.         }
  270.  
  271. }    /* WhatBranch */
  272.  
  273. /*****************************************************************************
  274.  * CreateBranch returns a node in the tree containing 'word'.
  275.  ****************************************************************************/
  276. static TreeType *CreateBranch(word,where)
  277.     char        *word;        /* The string to put in this node. */
  278.     long        where;        /* Index of the line the word is from. */
  279. {    TreeType    *node;        /* The node we are creating. */
  280.     ListType    *positions;    /* List with the positions. */
  281.  
  282.     if (debug)
  283.         fprintf(stderr,"CreateBranch working on %s %ld\n",word,where);
  284.  
  285.     if (node = (TreeType *)malloc(sizeof(TreeType)))
  286.         if (node->word = (char *)malloc(strlen(word) + 1))
  287.             {
  288.             node->left = node->right = (TreeType *)NIL;
  289.             strcpy(node->word,word);
  290.             if (where < 0)
  291.                 node->positions = (ListType *)NIL;
  292.             else if (positions = (ListType *)malloc(sizeof(ListType)))
  293.                 {
  294.                 positions->where = where;
  295.                 positions->next = (ListType *)NIL;
  296.                 node->positions = positions;
  297.                 }
  298.             else
  299.                 {
  300.                 free(node->word);
  301.                 free(node);
  302.                 node = (TreeType *)NIL;
  303.                 fprintf(stderr,"error: CreateBranch could not get memory for the index.\n");
  304.                 }
  305.             }
  306.         else
  307.             {
  308.             free(node);
  309.             node = (TreeType *)NIL;
  310.             fprintf(stderr,"error: CreateBranch could not get memory for the word [%s].\n",word);
  311.             }
  312.     else
  313.         fprintf(stderr,"error: CreateBranch could not get memory for the node.\n");
  314.  
  315.     return(node);
  316.  
  317. }    /* CreateBranch */
  318.  
  319. /*****************************************************************************
  320.  * BuildTree adds to the tree pointed to by 'root'.  No node will be added
  321.  * to the tree if 'word' already exists in the tree.
  322.  ****************************************************************************/
  323. void BuildTree(root,word,where)
  324.     TreeType    **root;        /* Root of the tree to build. */
  325.     char        *word;        /* The string to put in the tree. */
  326.     long        where;        /* Index of the line the word is from. */
  327. {    TreeType    *node;        /* The node we are adding. */
  328.  
  329.     if (!*root)
  330.         {
  331.         if (debug)
  332.             fprintf(stderr,"BuildTree creating the root\n");
  333.         *root = CreateBranch(word,where);
  334.         }
  335.     else if (!(node = WhatBranch(*root,word)))
  336.         {
  337.         node = CreateBranch(word,where);
  338.         switch (limb)
  339.             {
  340.             case GOLEFT:
  341.                 lastNode->left = node;
  342.                 break;
  343.             case GORITE:
  344.                 lastNode->right = node;
  345.                 break;
  346.             default:
  347.                 fprintf(stderr,"warning: BuildTree encountered bad default.\n");
  348.             }
  349.         }
  350.     else if (where >= 0)            /* Tree has a list in it. */
  351.         if (!InList(node,where))    /* word is already in the tree. */
  352.             node->positions = BuildList(node->positions,where);
  353.     /* else both word and where are already in the tree. */
  354.  
  355. }    /* BuildTree */
  356.  
  357. /*****************************************************************************
  358.  * NumberOfListNodes returns the number of nodes contained in the list
  359.  * 'positions'.
  360.  ****************************************************************************/
  361. long NumberOfListNodes(positions)
  362.     ListType    *positions;    /* List with the indexes. */
  363. {    long        num;        /* The number of nodes found. */
  364.  
  365.     for (num = 0; positions; positions = positions->next)
  366.         num++;
  367.     return(num);
  368.  
  369. }    /* NumberOfListNodes */
  370.  
  371. /*****************************************************************************
  372.  * LongestStr2tab returns the greatest number of characters prior to the tab
  373.  * character within the tree pointed to by 'node'.  This routine is used to
  374.  * give a formated output of the host and port contained at a given node.
  375.  ****************************************************************************/
  376. static int LongestStr2tab(node)
  377.     TreeType    *node;        /* The tree we are looking at. */
  378. {    static int    maxLen = 0;    /* Maximum length encountered. */
  379.     int        leftLen,    /* The max len found on the left side. */
  380.             riteLen;    /* The max len found on the right side. */
  381.  
  382.     if (!node)
  383.         return(maxLen);
  384.     else
  385.         {
  386.         leftLen = LongestStr2tab(node->left);
  387.         riteLen = LongestStr2tab(node->right);
  388.         maxLen  = MAX(maxLen,leftLen);
  389.         maxLen  = MAX(maxLen,riteLen);
  390.         maxLen  = MAX(maxLen,strchr(node->word,'\t') - node->word);
  391.         return(maxLen);
  392.         }
  393.  
  394. }    /* LongestStr2tab */
  395.  
  396. /*****************************************************************************
  397.  * PrintHostTree is the routine that actualy prints the contents of the tree
  398.  * pointed to by 'node'.  This routine prints the contents of the node such
  399.  * that the hostname will get printed followed by the port, where the port
  400.  * for all lines will be lined up.
  401.  ****************************************************************************/
  402. static void PrintHostTree(node,maxHostLen)
  403.     TreeType    *node;        /* The node to have printed. */
  404.     int        maxHostLen;    /* Max chars to a tab. */
  405. {    char        *tab,        /* Position of the tab. */
  406.             *hStr,        /* The host string. */
  407.             *pStr;        /* The port string. */
  408.  
  409.     if (!node)
  410.         return;
  411.     else
  412.         {
  413.         PrintHostTree(node->left,maxHostLen);
  414.  
  415.         /* Break the string up into the host and port parts. */
  416.         hStr = node->word;
  417.         tab = strchr(hStr,'\t');
  418.         *tab = '\0';
  419.         pStr = tab + 1;
  420.  
  421.         if (maxHostLen)
  422.             fprintf(stdout,"%*.*s\t%8s\n",-maxHostLen,maxHostLen,hStr,pStr),++lineNumber;
  423.         else
  424.             fprintf(stdout,"%s\n",hStr),++lineNumber;
  425.  
  426.         /* Restore the information in case we want to use it again. */
  427.         *tab = '\t';
  428.  
  429.         PrintHostTree(node->right,maxHostLen);
  430.         }
  431.  
  432. }    /* PrintHostTree */
  433.  
  434. /*****************************************************************************
  435.  * PrintTree is the routine that actualy prints the contents of the tree
  436.  * pointed to by 'node'.  This routine prints the contents of the node such
  437.  * that the hostname will get printed followed by the port, where the port
  438.  * for all lines will be lined up.
  439.  ****************************************************************************/
  440. void PrintTree(node,hostTree)
  441.     TreeType    *node;        /* The node to have printed. */
  442.     int        hostTree;    /* Are we printing the host tree? */
  443. {    ListType    *positions;    /* List with the positions. */
  444.  
  445.     if (hostTree)
  446.         PrintHostTree(node,(hostTree == 2) ? LongestStr2tab(node) : 0);
  447.     else if (!node)
  448.         return;
  449.     else
  450.         {
  451.         PrintTree(node->left,hostTree);
  452.         fprintf(stdout,"%d\t%s",strlen(node->word) + 1,node->word);
  453.         fprintf(stdout,"\t%ld",NumberOfListNodes(node->positions));
  454.         for (positions = node->positions; positions; positions = positions->next)
  455.             fprintf(stdout,"\t%ld", positions->where);
  456.         fprintf(stdout,"\n"),++lineNumber;
  457.         PrintTree(node->right,hostTree);
  458.         }
  459.  
  460. }    /* PrintTree */
  461.  
  462.